/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/4sum
   @Language: C++
   @Datetime: 17-01-08 21:10
   */

// Method 1 : Time O(n^3), Space O(1)
class Solution {
public:
	/**
	 * @param numbers: Give an array numbersbers of n integer
	 * @param target: you need to find four elements that's sum of target
	 * @return: Find all unique quadruplets in the array which gives the sum of 
	 *          zero.
	 */
	/** Tips : This is similar to problem 57 3sum, visit it for more
	 *  Time O(n^3) , Space O(1)
	 * */
	vector<vector<int> > fourSum(vector<int> A, int tar) {
		// write your code here
		vector<vector<int> > vs;
		sort(A.begin(),A.end());					// ascending order
		for(int i=0; i<A.size(); ++i){
			if (i>0 && A[i-1]==A[i]) continue;		// duplication
			for(int j=i+1; j<A.size(); ++j){
				if (j>i+1 && A[j-1]==A[j]) continue;// duplication
				for(int k=j+1, l=A.size()-1; k<l;){
					if (k>j+1 && A[k-1]==A[k]){
						++k;						// duplication
						continue;
					}
					if (l<A.size()-1 && A[l]==A[l+1]){
						--l;						// duplication
						continue;
					}
					int sum = A[i]+A[j]+A[k]+A[l];
					if (sum > tar) --l;
					else if (sum < tar) ++k;
					else {
						vector<int> v(4,A[i]);
						v[1]=A[j], v[2]=A[k++], v[3]=A[l--];
						vs.push_back(v);
					}
				}
			}
		}
		return vs;
	}
};


// Method 2 : Time O(k*n^2), Space O(k*n^2)
// k is the max count of the pair who have the same sum
/** Tips : using hash map to store each two nums' sum
 *         attention the duplication.
 *         after that, 4sum is transed to 3sum:
 *         find the A[i], A[j], and k in twosum that
 *         make their sum equal to target
 * */
class Solution {
public:
	// hash functional for hashing the vector<int>
	struct hashvec{
		size_t operator()(const vector<int> &v)const{
			string s;
			for (int i=0; i<v.size(); s+=" "+v[i++]);
			return hash<string>()(s);
		}
	};
	vector<vector<int>> fourSum(vector<int> A, int tar){
		// write your code
		sort(A.begin(), A.end());					// ascending order
		// using hash map to store the sum of A[i]+A[j] and index i,j
		unordered_map<int,vector<pair<int,int> > > twosum;
		for (int i=0; i<A.size(); ++i){
			if (i>0 && A[i-1]==A[i]) continue;		// skip duplication
			for (int j=i+1; j<A.size(); ++j) {
				if (j>i+1 && A[j-1]==A[j]) continue;// skip duplication
				twosum[A[i]+A[j]].push_back(make_pair(i,j));
			}
		}

		unordered_set<vector<int>,hashvec> cans;    // test duplication
		vector<vector<int> > res;					// results
		unordered_map<int,vector<pair<int,int> > >::iterator ts;
		vector<pair<int,int> >::iterator it;
		for (int i=2; i<A.size(); ++i) {
			for (int j=i+1; j<A.size(); ++j) {
				ts = twosum.find(tar-A[i]-A[j]);
				if (ts == twosum.end()) continue;   // can't find sum
				for (it=ts->second.begin(); it!=ts->second.end(); ++it){
					if (it->second >= i) continue;	// skip duplication
					vector<int> v(4, A[it->first]);
					v[1]=A[it->second], v[2]=A[i], v[3]=A[j];
					// add the v to both cans and res if cans has no v
					if (cans.find(v) == cans.end()){
						cans.insert(v);
						res.push_back(v);
					}
				}
			}
		}
		return res;
	}
};
